public class test {
}
 class BinaryTree {
    // 定义树节点结构
    static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    private TreeNode root;

    // 构造函数
    public BinaryTree() {
        root = null;
    }

    // 插入节点
    public void insert(int data) {
        root = insertRec(root, data);
    }

    private TreeNode insertRec(TreeNode root, int data) {
        if (root == null) {
            root = new TreeNode(data);
            return root;
        }

        if (data < root.data)
            root.left = insertRec(root.left, data);
        else if (data > root.data)
            root.right = insertRec(root.right, data);

        return root;
    }

    // 中序遍历 (左-根-右)
    public void inorderTraversal() {
        inorderRec(root);
    }

    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    // 前序遍历 (根-左-右)
    public void preorderTraversal() {
        preorderRec(root);
    }

    private void preorderRec(TreeNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preorderRec(root.left);
            preorderRec(root.right);
        }
    }

    // 后序遍历 (左-右-根)
    public void postorderTraversal() {
        postorderRec(root);
    }

    private void postorderRec(TreeNode root) {
        if (root != null) {
            postorderRec(root.left);
            postorderRec(root.right);
            System.out.print(root.data + " ");
        }
    }

    // 查找节点
    public boolean search(int data) {
        root = searchRec(root, data);
        return root != null;
    }

    private TreeNode searchRec(TreeNode root, int data) {
        if (root == null || root.data == data)
            return root;

        if (data < root.data)
            return searchRec(root.left, data);

        return searchRec(root.right, data);
    }

    // 主方法用于测试
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        // 插入节点
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // 遍历测试
        System.out.print("中序遍历: ");
        tree.inorderTraversal();
        System.out.println();

        System.out.print("前序遍历: ");
        tree.preorderTraversal();
        System.out.println();

        System.out.print("后序遍历: ");
        tree.postorderTraversal();
        System.out.println();

        // 搜索测试
        System.out.println("查找节点 40: " + tree.search(40));
        System.out.println("查找节点 90: " + tree.search(90));
    }
}
